/*
 * @Author: szx
 * @Date: 2021-12-27 16:07:31
 * @LastEditTime: 2021-12-27 16:26:30
 * @Description:
 * @FilePath: \leetcode\100-199\131\131.js
 */
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    const res = [];
    const len = s.length;
    const backtrack = (path, index) => {
        if (index >= len) {
            res.push(path.slice());
            return;
        }
        for (let i = index; i < len; i++) {
            if (!isPalindrome(s, index, i)) continue;
            path.push(s.substring(index, i + 1));
            backtrack(path, i + 1);
            path.pop();
        }
    };

    const isPalindrome = (s, start, end) => {
        for (let i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    };
    backtrack([], 0);
    return res;
};
console.log(partition('aab'));
